package com.note.feng.leetcode.algorithms.easy.tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class HundredFortyFive {

    /**
     * 145 二叉树的后序遍历
     * 给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
     *
     * 示例 1：
     *
     * 输入：root = [1,null,2,3]
     * 输出：[3,2,1]
     * 示例 2：
     *
     * 输入：root = []
     * 输出：[]
     * 示例 3：
     *
     * 输入：root = [1]
     * 输出：[1]
     *  
     * 提示：
     *
     * 树中节点的数目在范围 [0, 100] 内
     * -100 <= Node.val <= 100
     *
     * 进阶：递归算法很简单，你可以通过迭代算法完成吗？
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/binary-tree-postorder-traversal
     */
    /**
     *解法：
     * 后序遍历；先遍历左子树，再遍历右子树，最后输出父节点
     * 递归遍历：
     *
     * @param root
     * @return
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        tailOrder(root, list);
        return list;
    }

    private void tailOrder(TreeNode node, List<Integer> list){
        if(node == null){
            return;
        }
        tailOrder(node.left, list);
        tailOrder(node.right, list);
        list.add(node.val);
    }

    /**
     * 非递归后序遍历：
     * 若根节点不为空，入栈，根节点=左子节点，直到找到左子树的最后一个左子树；
     *
     * @param root
     * @return
     */
    public List<Integer> postorderTraversal2(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null){
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        while (root != null || !stack.isEmpty()){
            while (root != null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if(root.right == null || root.right == pre){
                list.add(root.val);
                pre = root;
                root = null;
            }else{
                stack.push(root);
                root = root.right;
            }
        }
        return list;
    }

    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
    }
}
